// https://www.lintcode.com/problem/construct-binary-tree-from-preorder-and-inorder-traversal/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // write your code here
        return _buildTree(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
    
    private TreeNode _buildTree(int[] preorder, int pstart, int pend, int[] inorder, int istart, int iend) {
        if (istart >= iend) {
            return null;
        }
        int i = istart;
        while (i < iend) {
            if (inorder[i] == preorder[pstart]) {
                break;
            }
            ++i;
        }
        TreeNode root = new TreeNode(preorder[pstart]);
        int llen = i - istart;
        root.left = _buildTree(preorder, pstart + 1, pstart + llen + 1, inorder, istart, i);
        root.right = _buildTree(preorder, pstart + llen + 1, pend, inorder, i + 1, iend);
        return root;
    }
}